二叉树的定义

「二叉树，Binary Tree」是一种非线性数据结构，表示着祖先与后代之间的派生关系，体现着“一分为二”的分治逻辑。

另一种定义：二叉是 n（n>=0）个结点的有限集合，该集合零个结点（空二叉树）或者一个根结点和两棵不互相交的、根节点的左/右子树组成。

其类似链表，也是 结点 为单位存储的。结点包括 值 和 两个指针

struct TreeNode {
	int val;         // 结点值
	TreeNode *left;  // 左子结点指针
	TreeNode *right; // 右子结点指针
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {};
};

结点的两个指针指向「左子结点，Left Child Node」和「右子结点，Right Child Node」，其称为左子结点和右子结点的「父节点，Parent Node」。

约定二叉树某结点，将左子结点以下的部分称为「左子树，Left SubTree」，右子结点以下的部分称为「右子树，Right SubTree」。

约定二叉树某结点，其没有两个子结点，称为「叶结点，Leaf Node」。

结点所拥有的子树的个数，称为 度